package com.st.shatangju8801.chapter01.zeroonepackege;

/**
 * 对于技术面试，你还在死记硬背么?
 * 快来“播”沙糖橘吧，
 * 用视频案例为你实战解读技术难点
 * 聚焦Java技术疑难点，实战视频为你答疑解惑
 * 越“播”越甜的沙糖橘，期待你的到来和参与 
 */
public class ZeroOnePackegeMain {
    // 0-1背包问题
    public static void main(String[] args) {
        // 定义物品的个数
        int n = 5;
        // 定义背包的容量
        int m = 10;
        // 定义物品的重量数组
        int w[] = {0, 2, 2, 6, 5, 4};
        // 定义物品的价值数组
        int v[] = {0, 6, 3, 5, 4, 6};
        // 定义状态转移二维数组
        //int k[][] = new int[n][m];
        // 变换的原因：算法描述中下标从1开始，java编码中下标从0开始，为了算法描述和算法java代码实现中保持一致，
        // 在下标为0的位置添加一个重量和价值都为0的物品进行填充
        int dp[][] = new int[w.length][m + 1];
        // 状态转移二维数组初始化
        // 根据不同的背包算法进行初始化
        // 0-1背包问题的状态转移方程组的初始化为：第一行全部初始化为0
        // int数组默认全部初始化为0，满足0-1背包的初始化条件，故，不再显式的进行初始化处理
        // 调用动态规划-背包算法
        // TODO 调用子算法
        // dp = test01(m, w, v);
        dp = test02(m, w, v);
        // 打印背包算法的结果
        System.out.println("动态规划-背包算法的最优解：" + dp[dp.length - 1][dp[0].length - 1]);
        // 打印动态规划算法过程
        printArr(dp);
        System.out.println("----------------------");
        int[] r = printResult(dp, w);
        System.out.println("动态规划的最优解（最大价值）构成的物品由：");
        printResult(r);
    }

    /**
     * 公众号沙糖橘：shatangju8801，请留意QQ交流群：798470346，沙糖橘社区倾心锻造~_~
     * <p>
     * 0-1背包问题算法1 - j下标正序遍历
     *
     * @param m 背包的最大容量
     * @param w 选择物品的重量数组
     * @param v 选择物品的价值数组
     * @return dp - 动态规划的状态二维数组
     */
    public static int[][] test01(int m, int w[], int v[]) {
        // 动态规划状态转移方程记录中间过程的二维数组
        int[][] dp = new int[w.length][m + 1];
        // 根据不同的背包算法进行初始化
        // 0-1背包问题的状态转移方程组的初始化为：第一行全部初始化为0
        // int数组默认全部初始化为0，满足0-1背包的初始化条件，故，不再显式的进行初始化处理
        // 动态规划的实现算法

        // i表示可以选择的物品个数， i 表示当前动态规划到的第i个物品
        for (int i = 1; i < w.length; i++) {
            // 遍历背包从1到最大值之间的每个可用容量的子过程的动态规划的最优解
            // j 表示当前背包的可用容量
            for (int j = 1; j < m + 1; j++) {
                // 装不下
                if (w[i] > j) {
                    // 选取上一步的规划结果作为当前步的最优解
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 装的下
                    // 需要在装入背包和不装入背包两种状态下的值进行比较，选取最值作为当前步的最优解
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
                }
            }
        }
        return dp;
    }

    /**
     * 公众号沙糖橘：shatangju8801，请留意QQ交流群：798470346，沙糖橘社区倾心锻造~_~
     * <p>
     * 0-1背包问题算法1 - j下标逆序遍历
     * 结论：在使用二维数组dp进行0-1背包算法实现时，背包的可用容量 j 变量在for循环中可以正序遍历也可以逆序遍历，计算结果是一样的。
     *
     * @param m 背包的最大容量
     * @param w 选择物品的重量数组
     * @param v 选择物品的价值数组
     * @return dp - 动态规划的状态二维数组
     */
    public static int[][] test02(int m, int w[], int v[]) {
        // 动态规划状态转移方程记录中间过程的二维数组
        int[][] dp = new int[w.length][m + 1];
        // 根据不同的背包算法进行初始化
        // 0-1背包问题的状态转移方程组的初始化为：第一行全部初始化为0
        // int数组默认全部初始化为0，满足0-1背包的初始化条件，故，不再显式的进行初始化处理
        // 动态规划的实现算法

        // i表示可以选择的物品个数， i 表示当前动态规划到的第i个物品
        for (int i = 1; i < w.length; i++) {
            // 遍历背包从1到最大值之间的每个可用容量的子过程的动态规划的最优解
            // j 表示当前背包的可用容量
            /*
            在使用二维数组dp进行0-1背包算法实现时，背包的可用容量 j 变量在for循环中可以正序遍历也可以逆序遍历，计算结果是一样的。
             */
            for (int j = m; j >= 1; j--) {
                // 装不下
                if (w[i] > j) {
                    // 选取上一步的规划结果作为当前步的最优解
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 装的下
                    // 需要在装入背包和不装入背包两种状态下的值进行比较，选取最值作为当前步的最优解
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
                }
            }
        }
        return dp;
    }

    /**
     * 公众号沙糖橘：shatangju8801，请留意QQ交流群：798470346，沙糖橘社区倾心锻造~_~
     * <p>
     * 遍历0-1背包最优解的构成内容
     *
     * @param k 状态转移二维数组，存储的动态规划每一步子过程的最优解
     * @param w 表示物品的重量维度
     * @return 物品是否装入背包的标记结果数组
     */
    public static int[] printResult(int[][] k, int[] w) {
        // 物品是否装入背包的标记数组
        int[] r = new int[k.length]; // 下标 i 表示第i个物品装入的结果：默认值 0 -- 未装入；1 -- 装入背包；
        // 初始化变量 i和j从k的最后一个元素开始向前进行回溯遍历
        // 物品的个数
        int i = k.length - 1;
        // 背包的当前的可用容量
        int j = k[0].length - 1;
        // 从k的最后一个元素开始向前进行回溯遍历
        while (i > 0 && j > 0) {
            // 判断当前物品i是否被装入了背包
            if (k[i][j] != k[i - 1][j]) {
                // 说明装入了物品i
                // 标记物品i的装入状态
                r[i] = 1;
                // 因为装入了物品i，所有背包的可用容量j需要发生更新
                j = j - w[i];
                // 遍历前一个物品
                i--;
            } else {
                // 物品i没有被装入，因为没有装入物品，所有j不需要更新
                // 遍历前一个物品
                i--;
            }
        }
        return r;
    }

    /**
     * 公众号沙糖橘：shatangju8801，请留意QQ交流群：798470346，沙糖橘社区倾心锻造~_~
     * <p>
     * 打印状态二维数组
     *
     * @param k 被打印的数组
     */
    public static void printArr(int[][] k) {
        if (k != null) {
            // 遍历行数
            for (int i = 0; i < k.length; i++) {
                // 遍历列数
                for (int j = 0; j < k[i].length; j++) {
                    System.out.print("  " + k[i][j]);
                }
                // 换行
                System.out.println();
            }
        }
    }

    /**
     * 公众号沙糖橘：shatangju8801，请留意QQ交流群：798470346，沙糖橘社区倾心锻造~_~
     * <p>
     * 打印动态规划结果标识数组
     * 元素值为1的是被标记为放入背包的物品
     *
     * @param r 标识数组
     */
    public static void printResult(int[] r) {
        if (r != null) {
            for (int i = 0; i < r.length; i++) {
                if (r[i] == 1) {
                    System.out.print("  物品" + i);
                }
            }
            // 换行
            System.out.println();
        }
    }
}